googologywikiaorg-20200223-history
Forum:Large numbers from finite promise games?
This posting by Friedman looks pretty interesting. I wonder if we could use it to define some super-fast growing function. --Ixfd64 (talk) 00:30, July 11, 2013 (UTC) From the posting, we have for example PROPOSITION 1.2. Let T be in PL and n >= 1. If m,s are sufficiently large then Bob wins G(T,n,s) even if Bob accepts all factorials > m offered by Alice. So we can set m = s, and define f(T, n) to be the the smallest t such that Bob wins G(T, n, s) for all s >= t. According to Friedman, f dominates all functions provably recursive in the theory ZFC + {there is a strongly k-Mahlo cardinal}_k. This is a very strong theory, so it will be a very fast growing function, faster than Loader's function I believe. Deedlit11 (talk) 13:16, July 11, 2013 (UTC) Do you know what subscript _k after extension of ZFC means? Also, is there any published proof of these results? It seems that we have winner in terms of fastest recursive function. LittlePeng9 (talk) 15:24, July 11, 2013 (UTC) :I believe it means that for each natural number k you add the axiom "There is a strongly k-Mahlo cardinal". As far as a published proof goes, it seems like Harvey Friedman makes a lot of posts to the F.O.M. mailing list including results that never get published in papers - perhaps he has to many. So I don't know if this particular theorem has a published proof anywhere. :Concerning the fastest recursive function, Friedman has some other results that result in faster growing functions: See for instance the papers "Finite functions and the Necessary Use of Large Cardinals" and "Finite Trees and the Necessary Use of Large Cardinals", both of which describe functions that dominate the provably recursive functions of the theory ZFC + {there exists a k-subtle cardinal}_k. Like this one, the theorems are fairly elementary, which is nice. :Actually, you can define a recursive function that dominates the provably recursive functions of any theory T (so you could take a really strong theory like ZFC + I0). Define f_T(n) to be the smallest m such that, for all Sigma^0_1 formulas of the form Ex A(x), if Ex A(x) is provable in T using fewer than n symbols, then A(x) is true for some x < m. This function will have the properties stated above, so it will be an extremely fast-growing function. Deedlit11 (talk) 14:18, July 12, 2013 (UTC) :I've heard about method in your last paragraph (Loader mentioned it in explantation of his program) but I did not suspect it could be possible to do in such strong system as ZFC (nuff said bout extensions). I really have to take a good look at FOM mailing when I have time! LittlePeng9 (talk) 19:39, July 12, 2013 (UTC) :I wouldn't be surprised if Friedman could beat any of us in a large number naming contest without breaking the Gentleman's Rule or using uncomputable functions. --Ixfd64 (talk) 21:41, July 12, 2013 (UTC)